package leetcode101;

import java.util.Scanner;

/**
 * @author shkstart
 * 链接：https://www.nowcoder.com/questionTerminal/c0a4b917a15f40a49ca10532ab9019fb
 * 来源：牛客网
 *
 * NowCoder号称自己已经记住了1-100000之间所有的斐波那契数。
 * 为了考验他，我们随便出一个数n，让他说出第n个斐波那契数。当然，斐波那契数会很大。因此，如果第n个斐波那契数不到6位，则说出该数；否则只说出最后6位。
 * @create 2023-01-11-23:10
 */
public class Meme32_1 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int arr[] = new int[100001];
        arr[0] = 0 ;
        arr[1] = 1 ;
        for (int i=2;i<arr.length;i++){
            arr[i] = arr[i-1]+arr[i-2];
        }
        while(scanner.hasNext()){
            int  n = scanner.nextInt();
            int result = arr[n]%100000;
            System.out.println();
        }
    }
}
